#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""
import sys
MAXINT = sys.maxsize
# MAXINT = sys.maxint     # py2


class DijkstraPath:
    def __init__(self, weight_matrix):
        self.n = len(weight_matrix)
        self.weight_matrix = weight_matrix
        # self.path_list = list(range(self.n))
        self.path_list = [0] * self.n

        self.undeter_node = set(range(1, self.n))
        self.deter_node = set([0])

        self.dijkstra()

    def dijkstra(self):
        while self.undeter_node:
            min_node = min(self.undeter_node, key=lambda k:self.weight_matrix[0][k])
            self.deter_node.add(min_node)
            self.undeter_node.remove(min_node)

            self.refresh_weight(min_node)

    def refresh_weight(self, node_idx):
        print('1')

        for idx in range(1, self.n):
            print('[node_idx] %s, idx [%s]' % (node_idx, idx))
            if idx == node_idx:
                continue

            weight0 = self.weight_matrix[0][node_idx]
            weight1 = self.weight_matrix[node_idx][idx]
            cand_weight = weight0 + weight1
            if weight1 == MAXINT:
                continue

            if cand_weight < self.weight_matrix[0][idx]:
                print('hit')
                self.weight_matrix[0][idx] = cand_weight
                self.path_list[idx] = node_idx

    def __str__(self):
        return str(self.path_list) + str(self.weight_matrix[0])

def main():
    print("start main")

    weight_matrix = [
      [0,       4,       MAXINT, MAXINT, MAXINT, MAXINT, MAXINT, 8,       MAXINT],
      [4,       0,       8,       MAXINT, MAXINT, MAXINT, MAXINT, 11,      MAXINT],
      [MAXINT, 8,       0,       7,       MAXINT, 4,       MAXINT, MAXINT, 2],
      [MAXINT, MAXINT, 7,       0,       9,       14,      MAXINT, MAXINT, MAXINT],
      [MAXINT, MAXINT, MAXINT, 9,       0,       10,      MAXINT, MAXINT, MAXINT],
      [MAXINT, MAXINT, 4,       14,      10,      0,       2,       MAXINT, MAXINT],
      [MAXINT, MAXINT, MAXINT, MAXINT, MAXINT, 2,       0,       1,       6],
      [8,       11,      MAXINT, MAXINT, MAXINT, MAXINT, 1,       0,       7],
      [MAXINT, MAXINT, 2,       MAXINT, MAXINT, MAXINT, 6,       7,       0]
    ]

    # weight_matrix = [
    #     [ 0,     1, 3, MAXINT],
    #     [ 1,     0, 1,  3],
    #     [ 3,     1, 0,  1],
    #     [MAXINT, 3, 1,  0],
    # ]

    d = DijkstraPath(weight_matrix)
    print(d)

if __name__ == "__main__":
    main()
